package interview.algorithms.again_in_interview;

import common.ListNode;
import common.TreeNode;
import common.Util;
import org.junit.Test;

import java.util.*;

import static common.Util.swap;

/**
 * @author fance
 * @date 2018/7/16 14:51
 */
public class Sum {
    public void sortColorsIII(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        int i = 0;
        while (i <= hi) {
            if (nums[i] == 0) {
                Util.swap(nums,lo,i);
                lo++;
            } else if (nums[i] == 2) {
                Util.swap(nums,i,hi--);
                i--;
            }
            i++;
        }
    }

    public int maxSubArraySum(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i < arr.length; i++) {
            cur += arr[i];
            max = Math.max(cur,max);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }

    public ListNode findKthToTail(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode fast = head,slow = head;
        while (fast != null && k-- > 0) {
            fast = fast.next;
        }
        if (k > 0) {
            return null;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public boolean hasLoop(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    public ListNode findPortLoop(ListNode head) {
        if (!hasLoop(head)) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    // 层序遍历二叉树  利用队列记录每一层节点个数
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while (!queue.isEmpty()) {
            int curSize = queue.size();
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < curSize; i++) {
                TreeNode cur = queue.poll();
                tmp.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tmp1 = headA;
        ListNode tmp2 = headB;
        int lenA = Util.getListLen(tmp1);
        int lenB = Util.getListLen(tmp2);
        ListNode tmp3 = headA;
        ListNode tmp4 = headB;
        if (lenA > lenB) {
            // 长的先走offset步
            for (int i = 0; i < lenA - lenB; i++) {
                tmp3 = tmp3.next;
            }
            while (tmp3 != tmp4) {
                tmp3 = tmp3.next;
                tmp4 = tmp4.next;
            }
            return tmp3;
        } else {
            // 长的先走offset步
            for (int i = 0; i < lenB - lenA; i++) {
                tmp4 = tmp4.next;
            }
            while (tmp3 != tmp4) {
                tmp3 = tmp3.next;
                tmp4 = tmp4.next;
            }
            return tmp3;
        }
    }

    public int majorityElementI(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    public int majorityElementII(int[] nums) {
        int majority = nums[0];
        int cnt = 1;
        for (int i = 1; i < nums.length; i++) {
            if (cnt == 0) {
                majority = nums[i];
                cnt++;
                continue;
            }
            if (nums[i] == majority) {
                cnt++;
            } else {
                cnt--;
            }
        }
        return majority;
    }

    /**
     * bf 统计
     * 一个数字出现一次，其他两次
     * @param a
     * @return
     */
    public int oddTimesNumI(int[] a) {
        int e0 = 0;
        for (int cur : a) {
            e0 ^= cur;
        }
        return e0;
    }

    public int[] oddTimesNumII(int[] a) {
        int e0 = 0, e0hasOne = 0;
        for (int cur : a) {
            e0 ^= cur;
        }
        int rightOne = e0 &(~e0 + 1);
        for (int cur : a) {
            if ((cur & rightOne) != 0) {
                e0hasOne ^= cur;
            }
        }
        int[] res = new int[2];
        res[0] = e0hasOne;
        res[1] = e0hasOne ^ e0;
        return res;
    }


    // 最小编辑距离
    public int minCost(String s1, String s2, int ic, int dc, int rc) {
        if (s1 == null || s2 == null) {
            return 0;
        }
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int rows = chars1.length + 1;
        int cols = chars2.length + 1;
        int[][] dp = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            dp[i][0] = dc * i;
        }
        for (int i = 0; i < cols; i++) {
            dp[0][i] = ic * i;
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (chars1[i - 1] == chars2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + rc;
                }

            }
        }
        return dp[rows - 1][cols - 1];
    }
    // LIS 最长递增子序列
    private int[] getDpForLIS(int[] a) {
        int[] dp = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
             }
        }
        return dp;
    }
    public int[] LIS(int[] a, int[] dp) {
        int len = 0;
        int index = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > len) {
                len = dp[i];
                index = i;
            }
        }
        int[] lis = new int[len];
        lis[--len] = a[index];

        for (int i = index; i >= 0; i--) {
            if (a[i] < a[index] && dp[i] == dp[index] - 1) {
                    lis[--len] = a[i];
                    index = i;
            }
        }
        return lis;
    }
    /**
     * 53. 最大子序和
     * 1.bf 2.贪心
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int maxSum = nums[0];
        int curSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (curSum < 0) {
                curSum = nums[i];
            } else {
                curSum += nums[i];
            }

            if (curSum > maxSum) {
                maxSum = curSum;
            }
        }
            return maxSum;

    }
    public List<Integer> getRightFirstMoreThanElement(int[] a) {
        List<Integer> res = new ArrayList<>();
        if (a == null || a.length < 2) {
            return res;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 1; i < a.length; i++) {
            while (!stack.isEmpty() && a[i] > a[stack.peek()]) {
                res.add(a[i]);
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }

    public List<Integer> getRightFirstMoreThanElementAgain(int[] a) {
        List<Integer> res = new ArrayList<>();
        if (a == null || a.length < 2) {
            return res;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 1; i < a.length; i++) {
            while (!stack.isEmpty() && a[i] > a[stack.peek()]) {
                res.add(a[i]);
                stack.pop();
            }
            stack.push(i);
        }
        return res;
    }
    /**
     * 1. Two Sum
     * 1.bf 2.排序 双指针 3.hashmap记录
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumI(int[] nums, int target) {
        int[] res = new int[2];
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        int cur;
        while (i < j) {
            cur = nums[i] + nums[j];
            if (cur == target) {
                res[0] = i;
                res[1] = j;
                return res;
            } else if (cur > target) {
                j--;
            } else {
                i++;
            }
        }
        return res;
    }
    public int[] twoSumII(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                res[0] = map.get(nums[i]);
                res[1] = i;
                return res;
            } else {
                map.put(target - nums[i],i);
            }
        }
        return res;
    }

    private int findFirstIndex(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > target) {
                hi = mid - 1;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else if (mid != 0 && nums[mid] == nums[mid - 1]) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    public void quickSort(int[] a) {
        quickSort(a,0,a.length - 1);

    }
    /**
     * 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    public boolean hasPath(char[][] m, int rows,int cols,char[] s) {
        if (rows == 0 || cols == 0) {
            return false;
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hasPathCore(m,rows,cols,s,new boolean[rows][cols],0,i,j)) {
                    return true;
                }
            }
        }
        return false;
    }
    public boolean hasPathCore(char[][] m, int rows,int cols,char[] s,boolean[][] used,int path,int r,int c) {
        if (path == s.length) {
            return true;
        }
        if (r < 0 || r >= rows || c < 0 || c >= cols) {
            return false;
        }
        if (m[r][c] != s[path]) {
            return false;
        }
        if (used[r][c]) {
            return false;
        }
        used[r][c] = true;
        if (hasPathCore(m,rows,cols,s,used,path + 1, r + 1,c) ||
                hasPathCore(m,rows,cols,s,used,path + 1, r - 1,c) ||
                hasPathCore(m,rows,cols,s,used,path + 1, r,c + 1) ||
                hasPathCore(m,rows,cols,s,used,path + 1, r,c - 1)) {
            return true;
        }
            used[r][c] = false;
        return false;
        }

    /**
     * 15
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForSubsets(res,new ArrayList<>(),nums,0);
        return res;
    }
    private void backtrackForSubsets(List<List<Integer>> res,List<Integer> tmpLilst, int[] nums,int start) {
        res.add(new ArrayList<>(tmpLilst));
        for (int i = start; i < nums.length; i++) {
            tmpLilst.add(nums[i]);
            backtrackForSubsets(res,tmpLilst,nums,i + 1);
            tmpLilst.remove(tmpLilst.size() - 1);
        }
    }
    public List<List<Integer>> subsetsAgian(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForSubsetsAgian(res,new ArrayList<>(),nums,0);
        return res;
    }
    private void backtrackForSubsetsAgian(List<List<Integer>> res,List<Integer> tmpLilst, int[] nums,int start) {
        res.add(new ArrayList<>(tmpLilst));
        for (int i = start; i < nums.length; i++) {
            tmpLilst.add(nums[i]);
            backtrackForSubsetsAgian(res,tmpLilst,nums,i + 1);
            tmpLilst.remove(tmpLilst.size() - 1);
        }
    }
        public void quickSort(int[] a,int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int j = partition(a,lo,hi);
        quickSort(a,lo,j - 1);
        quickSort(a,j + 1,hi);
    }
    public int partition(int[] a,int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    int v = a[lo];
    while (true) {
        while (a[++i] < v) {
            if (i == hi) {
                break;
            }
        }
        while (a[--j] > v) {
            if (j == lo) {
                break;
            }
        }

        if (i >= j) {
            break;
        }
        Util.swap(a,i,j);
    }
    Util.swap(a,lo,j);
    return j;
}

    int leftChild(int i) {
        return 2 * i + 1;
    }
    void sink(int[] a, int i, int n) {
        int child;
        int tmp = a[i];
        for (;leftChild(i) < n;i = child) {
            child = leftChild(i);
            if (child != n - 1 && a[child + 1] > a[child]) {
                child++;
            }
            if (tmp < a[child]) {
                a[i] = a[child];
            } else {
                break;
            }
        }
        a[i] = tmp;
    }
    void heapSort(int[] a, int n) {
        for (int i = n / 2; i >= 0; i--) {
            sink(a,i,n);
        }
        for (int i = n - 1; i > 0; i--) {
            swap(a,0, i);// delMax
            sink(a,0, i);
        }
    }


    static int[] tmp;
    void merge(int[] a, int lo, int mid, int hi) {
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            tmp[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = tmp[j++];
            } else if (j > hi) {
                a[k] = tmp[i++];
            } else if (tmp[i] < a[j]) {
                a[k] = tmp[i++];
            } else {
                a[k] = tmp[j++];
            }
        }
    }
    void mergeSort(int[] a, int n) {
        tmp = new int[n];
        mergeSort(a, 0, n - 1);
    }
    void mergeSort(int[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid);
        mergeSort(a, mid + 1, hi);
        merge(a, lo, mid, hi);
    }

    void insertSort(int[] a, int n) {
        for (int i = 1; i < n; i++) {
            int tmp = a[i];
            int j = i;
            for (; j > 0 && a[j - 1] > tmp;j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }
    void shellSort(int[] a, int n) {
        for (int increment = n / 2; increment > 0; increment /= 2) {
            for (int i = increment; i < n; i++) {
                int tmp = a[i];
                int j = i;
                for (; j >= increment; j -= increment) {
                    if (tmp < a[j - increment]) {
                        a[j] = a[j - increment];
                    } else {
                        break;
                    }
                }
                a[j] = tmp;
            }
        }
    }
    public void bubbleSort(int[] a,int n) {
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                if (a[j] > a[j + 1]) {
                    Util.swap(a,j,j + 1);
                }
            }
        }    
    }
    public void bubbleSortII(int[] a,int n) {
        boolean flag = true;
        for (int i = 1; i < n && flag; i++) {
            flag = false;
            for (int j = 0; j < n - i; j++) {
                if (a[j] > a[j + 1]) {
                    Util.swap(a,j,j + 1);
                    flag = true;
                }
            }
        }
    }
    void selectSort(int[] a, int n) {
        for (int i = 0; i < n - 1; i++) {
            int small = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[small]) {
                    small = j;
                }
            }
            if (small != i) {
                swap(a, i, small);
            }
        }
    }
    void cntSort(int[] a, int n) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        int[] cnt = new int[max + 1];
        for (int i = 0; i < n; i++) {
            cnt[a[i]]++;
        }
        int index = 0;
        for (int i = 0; i < max + 1; i++) {
            while (cnt[i]-- != 0) {
                a[index++] = i;
            }
        }
    }

    //  topK 1.排序 2.最小堆 3.快速选择
    public int kThLargestII(int[] a, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < a.length; i++) {
            minHeap.offer(a[i]);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

    public int kThLargestIII(int[] a, int k) {
        k = a.length - k;
        int lo = 0;
        int hi = a.length - 1;
        while (lo < hi) {
            int j = partition(a, lo, hi);
            if (j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return a[k];

    }

    public ListNode josephusKill(ListNode head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }
        ListNode last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = head;  // 成环。
        int cnt = 0;
        while (head != last) {
            if (++cnt == m) {
                last.next = head.next;
                cnt = 0;
            } else {
                last = last.next;
            }
            head = last.next;
        }
        return head;
    }
    public int getResult(int n, int m) {
        int num[] = new int[n];
        int count = n;
        int step = 0;
        int i = -1;
        while (count>0) {
            i++;
            if (i >= n) {
                i = 0;
            }
            if (num[i] == -1) {
                continue;
            }

                step++;
            if (step == m) {
                num[i] = -1;
                step = 0;
                count -=1;
            }

        }
        return i + 1;
    }
    int josephusII(int n,int m) {
        if (n == 1) {
            return 0;
        } else {
            return (josephusII(n - 1,m) + m) % n;
        }
    }
    int josephusIII(int n,int m) {
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }

    public ArrayList<Integer> inOrderUnRecur(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root != null) {
            LinkedList<TreeNode> stack = new LinkedList<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    TreeNode cur = stack.pop();
                    res.add(cur.val);
                    root = cur.right;
                }
            }
            }
            return res;
    }
    public ArrayList<Integer> inOrderUnRecurAgain(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if (root != null) {
            LinkedList<TreeNode> stack = new LinkedList<>();
            while (!stack.isEmpty() || root != null) {
                if (root != null) {
                    stack.push(root);
                    root = root.left;
                } else {
                    TreeNode cur = stack.pop();
                    res.add(cur.val);
                    root = cur.right;
                }
            }
        }
        return res;
    }


        @Test
    public void test() {

       /* Random random = new Random(47);
        int[] a = new int[1000];
        for (int i = 0; i < 1000; i++) {
            a[i] = random.nextInt();
        }
        long st = System.currentTimeMillis();*/
        int[] a = {10,23,33,9,101};
        List<Integer> res = getRightFirstMoreThanElement(a);
        for (int i : res) {
            System.out.print(i + " ");
        }
//        quickSort(a);
// 47 bubbleSort(a,a.length);
// 46 bubbleSortII(a,a.length);
     /*   for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        System.out.println(System.currentTimeMillis() - st);
    */}

}
